/****************************************************************************\
*                                                                            *
*  Copyright 2008 The CAnt2 Project (http://code.google.com/p/cant2)         *
*                                                                            *
*  Licensed under the Apache License, Version 2.0 (the "License");           *
*  you may not use this file except in compliance with the License.          *
*  You may obtain a copy of the License at                                   *
*                                                                            *
*      http://www.apache.org/licenses/LICENSE-2.0                            *
*                                                                            *
*  Unless required by applicable law or agreed to in writing, software       *
*  distributed under the License is distributed on an "AS IS" BASIS,         *
*  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.  *
*  See the License for the specific language governing permissions and       *
*  limitations under the License.                                            *
*                                                                            *
\****************************************************************************/

#include "EnableIf.h"

template < typename T, unsigned N > class CircularQueue
{
public:
    CircularQueue()
        : in    ( 0 )
        , out   ( 0 )
        , used  ( 0 )
    {
    }

    void Enqueue ( T& data )
    {
        if ( used == N ) throw std::runtime_error ( "Full" );
        swap ( buffer[in], data );
        in = ModAdvance<N> ( in, 1 );
        used += 1;
    }

    void Dequeue ( T& data )
    {
        if ( used == 0 ) throw std::runtime_error ( "Empty" );
        swap ( data, buffer[out] );
        out = ModAdvance<N> ( out, 1 );
        used -= 1;
    }

    const T& Peek ( unsigned n )
    {
        if ( n >= used ) throw std::runtime_error ( "Too empty" );
        unsigned p = ModAdvance<N>( out, n );
        return buffer [ p ];
    }

    unsigned Used() const
    {
        return used;
    }

    unsigned Capacity() const
    {
        return N;
    }

private:
    template < unsigned M > static typename EnableIf<((M&(M-1))!=0),unsigned>::Type ModAdvance ( unsigned p, unsigned d )
    {
        p += d;
        p %= M;
        return p;
    }

    template < unsigned M > static typename EnableIf<((M&(M-1))==0),unsigned>::Type ModAdvance ( unsigned p, unsigned d )
    {
        p += d;
        p &= M-1;
        return p;
    }

private:
    CircularQueue ( const CircularQueue& );
    CircularQueue& operator = ( const CircularQueue& );

private:
    unsigned in;
    unsigned out;
    unsigned used;
    T buffer[N];
};

